package leetcode1;

public class Day20 {
    //整数替换，贪心算法
    public int integerReplacement(int n) {
        if(n == 1) return 0;
        int ret=0;
        while(n > 1) {
            if(n%2==0) {
                //偶数
                ret++;
                n/=2;
            }else {
                //奇数
                if(n==3) {
                    ret+=2;
                    n=1;
                }else {
                    //判断-1或者+1
                    if(n%4==1) {
                        n/=2;
                        ret+=2;
                    }
                    else {
                        n=n/2+1;
                        ret+=2;
                    }
                }
            }
        }
        return ret;
    }
}
